#include <bits/stdc++.h>
const int N = 1e5 + 5; 
using namespace std; 
int n, m, q, k, ans; 
int a[N], b[N]; 
inline void dfs(int x) {
	if(x == q + 1) {
		for(int i = 1; i <= n - m + 1; ++i) {
			bool flag = 1; 
			for(int j = i; j <= i + m - 1; ++j)
				if(a[j] ^ b[j - i + 1]) {
					flag = 0; 
					break; 
				}
			if(flag) ++ans; 
		}
		return ; 
	}
	for(int i = 1, lst; i <= n; ++i)
		for(int j = 1; j <= k; ++j)
			lst = a[i], a[i] = j, dfs(x + 1), a[i] = lst; 
	return ; 
}
inline void solve() {
	cin >> n >> m >> q >> k; 
	if(q < m || n < m) return cout << "0\n", void(); 
	for(int i = 1; i <= m; ++i) cin >> b[i]; 
	dfs(1); 
	cout << ans << "\n"; 
	return ; 
}
int main() {
	freopen("sequence.in", "r", stdin); 
	freopen("sequence.out", "w", stdout); 
	ios::sync_with_stdio(false); 
	cin.tie(0); cout.tie(0); 
	solve(); 
	return 0; 
}
